package algorithm;

import java.util.Arrays;

/**
 * @Description: 快速排序
 * @Author: hmm
 * @CreateDate: 2019/8/26
 * @UpdateUser:
 * @UpdateDate: 2019/8/26
 * @UpdateRemark: 修改备注
 * @Version: 1.0
 */
public class QuickSort {

    public static void quickSort(int[] arr,int left, int right) {
        int i, j, t, key;
        //left 必须小于 right
        if(left > right) {
            return;
        }
        //以left的值作为基准值
        key = arr[left]; //temp中存的就是基准数
        i = left;
        j = right;
        while(i != j) { //顺序很重要，要先从右边开始找
            while(arr[j] >= key && i < j) {
                j--;
            }
            while(arr[i] <= key && i < j){//再找右边的
                i++;
            }
            if(i < j)//交换两个数在数组中的位置
            {
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        //最终将基准数归位
        arr[left] = arr[i];
        arr[i] = key;
        quickSort(arr,left, i-1);//继续处理左边的，这里是一个递归的过程
        quickSort(arr,i+1, right);//继续处理右边的 ，这里是一个递归的过程
    }

    public static void main(String[] args) {
        int[] arr = {4,12,1,55,15,47,21,56,13};
        QuickSort.quickSort(arr, 0, 8);
        System.out.println(Arrays.toString(arr));
    }
}
